// 1143. 最长公共子序列     //			剑指 Offer Ⅱ 95
// 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

// 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

// 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
// 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

//  

// 示例 1：

// 输入：text1 = "abcde", text2 = "ace" 
// 输出：3  
// 解释：最长公共子序列是 "ace" ，它的长度为 3 。
// 示例 2：

// 输入：text1 = "abc", text2 = "abc"
// 输出：3
// 解释：最长公共子序列是 "abc" ，它的长度为 3 。
// 示例 3：

// 输入：text1 = "abc", text2 = "def"
// 输出：0
// 解释：两个字符串没有公共子序列，返回 0 。
//  

// 提示：

// 1 <= text1.length, text2.length <= 1000
// text1 和 text2 仅由小写英文字符组成。


// dp(s1, i, s2, j) 表示的是s1[i...] s2[j...] 长度内的最长公共子序列
#include<bits/stdc++.h>
#include<vector>
using namespace std;

// int dp(string s1, size_t i, string s2, size_t j) {

// 	//base case
// 	if (i == s1.size() || j == s2.size()) {
// 		return 0;
// 	}

// 	// 如果之前计算过，则直接返回
// 	if (memo[i][j] != -1) {
// 		return memo[i][j];
// 	}

// 	if (s1[i] == s2[j]) {
// 		memo[i][j] = 1 + dp(s1, i + 1, s2, j + 1);
// 	}
// 	else {
// 		memo[i][j] = max(dp(s1, i + 1, s2, j), dp(s1, i, s2, j + 1));
// 	}

// 	return memo[i][j];
// }

int longestCommonSubsequence(string text1, string text2) {
	int m = text1.length(), n = text2.length();
	// int dp[m + 1][n + 1];		// 备忘录用以消除重叠子问题
	vector<vector<int>> dp(m + 1, vector<int>(n + 1));

	for (int i = 1; i <= m; ++i) {
		char c1 = text1.at(i - 1);
		for (int j = 1; j <= n; ++j) {
			char c2 = text2.at(j - 1);
			if (c1 == c2) {
				dp[i][j] = 1 + dp[i - 1][j - 1];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	return dp[m][n];
}


int main(){
	string s1 = "abcde", s2 = "ace";
	int ans = longestCommonSubsequence(s1, s2);
	printf("%d\n", ans);
}